# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.val)


class Solution:
    def preorderTraversal(self, root: TreeNode):
        result = []
        heap = []
        if root is None:
            return result
        tmp = root
        while tmp or len(heap):
            if tmp:
                result.append(tmp.val)
                if tmp.left is None:
                    tmp = tmp.right
                else:
                    heap.append(tmp)
                    tmp = tmp.left
            else:
                tmp = heap.pop(-1)
                if tmp.right:
                    tmp = tmp.right
                else:
                    tmp = None
        return result


if __name__ == '__main__':
    so = Solution()
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    result = so.preorderTraversal(root)
    print(result)
